import bean.ListNode;

public class LeetCode19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fastNode = head;

        int num = 1;
        while (fastNode != null){
            if (fastNode.next == null ){
                break;
            }

            if (fastNode.next.next == null){
                num++;
                break;
            }

            fastNode = fastNode.next.next;
            num += 2;
        }

//        System.out.println("num:" + num);

        ListNode currentNode = head;
        ListNode lastNode = null;
        for (int i = 0; i < num; i++){
           if (i == num - n){
                if (lastNode == null && currentNode.next != null){
                    head = currentNode.next;
                    break;
                }

                if (lastNode == null && currentNode.next == null){
                    return null;
                }

                lastNode.next = currentNode.next;

                break;
           }else {
               lastNode = currentNode;
               currentNode = currentNode.next;
           }
        }

        return head;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode temp = new ListNode(0, head);
        ListNode fast = head;
        ListNode low = temp;
        int k = 0;
        while(k < n){
            fast = fast.next;
            k++;
        }

        while(fast != null){
            fast = fast.next;
            low = low.next;
        }

        if(low.next != null){
            low.next = low.next.next;
        }


        return temp.next;
    }


}
